﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TrieUtils
{
    internal class Trie<T>
    {
        private Dictionary<char, Trie<T>> _index = new Dictionary<char, Trie<T>>();
        private HashSet<T> _storedItems;

        internal void Add(T content)
        {
            string contentName = content.ToString().ToLower();

            while (contentName.Length > 0)
            {
                Add(content, contentName);
                contentName = contentName.Substring(1);
            }
        }

        internal IEnumerable<T> FindItems(string pattern, int limit)
        {
            Trie<T> currentTrie = this;
            pattern = pattern.ToLower();

            foreach (var c in pattern)
            {
                if (!currentTrie._index.TryGetValue(c, out currentTrie))
                    return Enumerable.Empty<T>();
            }

            return currentTrie.GetCurrentItems(limit);
        }

        private IEnumerable<T> GetCurrentItems(int limit)
        {
            if (_storedItems != null)
            {
                foreach (var item in _storedItems)
                {
                    yield return item;
                    limit--;

                    if (limit <= 0)
                        yield break;
                }
            }
        }

        private void Add(T content, string contentNameLeft)
        {
            StoreContent(content);

            if (contentNameLeft.Length > 0)
                BuildIndex(content, contentNameLeft);
        }

        private void BuildIndex(T content, string contentNameLeft)
        {
            char indexCharacter = contentNameLeft[0];
            contentNameLeft = contentNameLeft.Substring(1);

            if (!_index.ContainsKey(indexCharacter))
                _index.Add(indexCharacter, new Trie<T>());

            _index[indexCharacter].Add(content, contentNameLeft);
        }

        private void StoreContent(T content)
        {
            if (_storedItems == null)
                _storedItems = new HashSet<T>();

            _storedItems.Add(content);
        }
    }
}
